package class_08;

/**
   *    汉诺塔问题
 * @author LOGAN
 *划分子问题：
* 过程：
1、先把1~n-1从from移动到help；
2、把单独的n移动到to；
3、1~n-1从help移动到to；
	时间复杂度就是：T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1)+1（一个等比公式）。
	T(n-1)是移动到help；1是从from直接移动到to；T(n-1)是把全部n-1挪回去。总的步数是2的N次方减一。
左   
 */
public class Code_02_Hanoi {

	public static void hanoi(int n) {
		if (n > 0) {
			func(n, n, "left", "mid", "right");
		}
	}
	/**
	 * down 
	 * rest 
	 * @param rest  代表是那个数
	 * @param down	代表放下的是几
	 * @param from	从哪里
	 * @param help	辅助
	 * @param to	到哪里
	 */
	public static void func(int rest, int down, String from, String help, String to) {
		if (rest == 1) {
			System.out.println("move " + down + " from " + from + " to " + to);
		} else {
			func(rest - 1, down - 1, from, to, help);
			func(1, down, from, help, to);
			func(rest - 1, down - 1, help, from, to);
		}
	}

	public static void moveLeftToRight(int N) {
		if (N == 1) {
			System.out.println("move 1 from left to right");
		}
		moveLeftToMid(N - 1);
		System.out.println("move " + N + "from left to right");
		moveMidToRight(N - 1);
	}

	public static void moveRightToLeft(int N) {

	}

	public static void moveLeftToMid(int N) {
		if (N == 1) {
			System.out.println("move 1 from left to mid");
		}
		moveLeftToRight(N - 1);
		System.out.println("move " + N + "from left to mid");
		moveRightToMid(N - 1);
	}

	public static void moveMidToLeft(int N) {

	}

	public static void moveRightToMid(int N) {

	}

	public static void moveMidToRight(int N) {
		if (N == 1) {
			System.out.println("move 1 from mid to right");
		}
		moveMidToLeft(N - 1);
		System.out.println("move " + N + "from mid to right");
		moveLeftToRight(N - 1);
	}

	public static void main(String[] args) {
		int n = 3;
		hanoi(n);
	}

}
